yupsung Computer Science blog

05_3 : Semi-Supervised Learning : Graph-based SSL 이번 글에서는 Graph 기반의 Semi-Supervised Learning을 알아보자. Graph-based SSL 가장 기본적인 아이디어는 우리에게 주어진 Data instance들을 Graph의 Node로 표현하고, 각 Data들의 유사성을 Edge로 표현하는 것이다. 여기서 가정은 아래와 같다. A graph is given on the labeled and unlabeled data Instances connected by heavy edge tend to have the same label 구성된 Graph에 대하여 두 instance가 heavy edge, 강한 연결관계를 갖고있다면 두 Instance가 동일한 label일 가능성이 높다고 간주한다. Graph Construction Nodes : $X_l \cup X_u$ Edges : Similarity weights computed from features, e.g. K-nearest neighbor graph : Unweighted (0 or 1 weights) Fully connected graph, weight decays with distance $$ w_{ij} = exp \big(\frac{-||x_i - x_j ||^2} { \sigma^2 } \big) $$ $\epsilon$-radius graph K-nearest neighbor (KNN) 방법은 가장 가까운 K개를 1 weight로 연결한다. 때문에 data의 밀도를 고려하지 못하는 단점이 있다. Fully connected graph의 경우, 모든 경우를 표현하지만, Graph의 크기가 너무 커진다는 단점이 있다. $\epsilon$-radius graph 방법은, 거리가 일정 Cut-off 이하인 Node들 만을 Edge로 연결한다. 이 경우 data의 밀도를 고려 가능하지만, 모든 instance가 연결된다는 보장이 없다는 단점

 05_2 : Semi-Supervised Learning : Self-Training and Co-Training 우선 가장 기본적인 준지도학습 방법 Self-Training에 대하여 알아보자.  Self-Training 우리에게 주어진 정보는 Labeled data $(\mathbf{X}_l,y_l)$과 Unlabeled data $\mathbf{X}_u$이다. Self-training과정은 다음과 같이 진행된다.  1. 우선 주어진 Labeled data $(\mathbf{X}_l,y_l)$를 사용하여 예측함수 $f$를 학습시킨다. $$y_l = f(x_l)$$ 2. 학습이 완료되면, 예측함수 $f$를 사용해 Unlabeled data $\mathbf{X}_u$의 예측값 $\hat{y}_u$를 구한다. $$\hat{y}_u = f(x_u)$$ $$\Downarrow$$ 3. 이제 기존의 Labeled data와 예측함수에 의해 labeling이 된 Unlabeled data를 합치고, 이 data를 사용해 예측함수 $g$를 학습한다. 이때 어떻게 Unlabeled data를 합치는지에 따라서 많은 variation이 있다. 대표적으로 Add all $(x_u,\hat{y}_u)$ to labeled data Add a few most confident $(x_u,\hat{y}_u)$ to labeled data Add all $(x_u,\hat{y}_u)$ to labeled data, weight each by confidence. 모든 Unlabeled data를 합치는 방법, 몇몇개의 가장 예측 confidence가 높은 data만을 합치는 방법, 모든 data를 합치치만 예측 confidence에 따라서 weight를 지정하는 방법 등이 있다. 4. 위와 같은 과정을 Unlabeled data가 없어지거나, 수렴할 때 까지 반복한다. Propagating 1-Nearest Neighbor 다른 예시로 Propagating 1-Nearest Neig

05_1 : Semi-Supervised Learning : Overview 이번 글에서는 Semi-Supervised Learning 준지도학습이 어떤 것인지, 목적이 무엇인지 알아볼 것이다. Machine Learning Categories 일반적으로 Machine Learning 방법은 크게 두가지로 분류된다. Supervised Learning (지도학습) 모든 Data에 Labeling이 완료되어, 입력 X와 출력 Y를 알고있다. 학습을 통해서 $f(x)=y$를 잘 추정하는 함수 $f$를 찾는 것이 목적이다. Unsupervised Learning (비지도학습) Data의 Labeling이 수행되지 않았고, 입력 X만을 알고있다. 학습을 통해서 data 고유의 특징이나 분포를 찾는 것이 목적이다. 그렇다면 지도학습을 하려 하는데, 아래와 같이 $N$개의 데이터에 대해서는 $Y$값을 알고있지만 나머지 $M$개에 대해서는 $Y$값을 모른다. 그렇다면 $M$개의 data는 그냥 사용하지 못하고 버려야 하는걸까? 우리가 지금부터 알아볼 Semi-supervised Learning (준지도학습) 은 unlabeled된 $M$개의 data도 학습에 활용하여 labeled된 data만 사용한 Supervised Learning보다 더 좋은 성능의 모델을 만들고자한다. Backgrounds 준지도학습이라는 방법이 만들어진 계기는, Labeling을 하는 것이 매우 비싸고 소모적이기 떄문이다. 일반적으로 Machine Learning에 사용할 데이터는 Row Data인 경우가 많다. 이를 지도학습에 사용하기 위해서 인력과 시간과 돈을 들여 일일이 Labeling을 하는 과정이 필요하다. 의료 data와 같이 Data를 전문가만 이해할 수 있고 labeling이 가능한 경우도 있고, 반도체 공정 data와 같이 최첨단 장비를 사용해 검사를 수행해야 labeling이 가능한 경우도 있다. 중국어 data와 같은 경우 4000문장을 labeling하는 과정에서 4년이 걸렸